-- 题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

-- 　　比如将二元查找树
--                10
--             /      \
--            6       14
--          /  \     /　 \
--         4     8  12 　 16
-- 转换成双向链表

-- 4=6=8=10=12=14=16。

-- 前序遍历 访问根节点 ,前序遍历左子树 , 前序遍历有字数

-- 中序遍历 访问左  根 右

-- 后序遍历 访问左 右 根

local BSTreeNode = {
	m_nvalue = -1 , --默认值为-1
	m_pLeft = nil, --左孩子
	m_pRight = nil, --右孩子
	m_height = 0 ; --以当前节点为根节点的树高
}

function getHeight(pNode)
	return pNode == nil and -1 or pNode.m_height
end

--构造平衡二叉树
--        3      
--       2   ->   2
--      1        1  3
--
--左左情况进行右旋
function RightRotate(pNode)

	local s = pNode.m_pLeft ;  --拿到旋转节点的左节点
	pNode.m_pLeft = s.m_pRight ; -- 当前节点的左节点变为之前左节点的右节点
	s.m_pRight = pNode ; -- 新节点的右节点指向 上个根节点
	--重新计算树高
	pNode.m_height = math.max(getHeight(pNode.m_pLeft),getHeight(pNode.m_pRight)) + 1;
	s.m_height = math.max(getHeight(s.m_pLeft),pNode.m_height)+1; 
	return s ;

end

--     以最上节点为对象进行旋转
--      1      
--       2   ->    2
--        3       1 3
--
--右右情况进行左旋
function LeftRotate(pNode)

	local s = pNode.m_pRight ;  --拿到旋转节点的左节点
	pNode.m_pRight = s.m_pLeft ; -- 当前节点的左节点变为之前左节点的右节点
	s.m_pLeft = pNode ; -- 新节点的右节点指向 上个根节点
	--重新计算树高
	pNode.m_height = math.max(getHeight(pNode.m_pLeft),getHeight(pNode.m_pRight)) + 1;
	s.m_height = math.max(getHeight(s.m_pLeft),pNode.m_height)+1; 
	return s ;

end


---左右情况	先左旋再右旋
function LeftRightRotate(pNode)
	local s = LeftRotate(pNode.m_pLeft) ;
	return RightRotate(s) ;
end


---右左情况 先右旋在左旋
function RightLeftRotate(pNode)
	local s  = RightRotate(pNode.m_pRight)
	return LeftRotate(s);
end

--插入节点,构造平衡二叉树
function insertNode(data,pNode)
	if(not pNode) then
		return {m_nvalue = data,m_height=0} ;
	end 	
 	--插入左节点
 	if data < pNode.m_nvalue then
 		--返回左节点数的根节点
 		pNode.m_pLeft = insertNode(data,pNode.m_pLeft) ;
 		--唯一的可能就是2 需要旋转
 		if(getHeight(pNode.m_pLeft)-getHeight(pNode.m_pRight)==2) then
 			--判断是需要进行一次旋转还是进行两次旋转   只有右边节点多了才需要两次旋转左右
 			 if(data<pNode.m_pLeft.m_nvalue) then
 			 	pNode = RightRotate(pNode);
 			 else
 			 	pNode = LeftRightRotate(pNode)
 			 end

 		end

 	else
 		pNode.m_pRight = insertNode(data,pNode.m_pRight);
 		if(getHeight(pNode.m_pRight)-getHeight(pNode.m_pLeft)==2) then
 			if(data<pNode.m_pRight.m_nvalue) then
 				pNode = RightLeftRotate(pNode) ;
 			else
 				pNode = LeftRotate(pNode);
 			end
 		end
 	end
 	pNode.m_height = math.max(getHeight(pNode.m_pLeft),getHeight(pNode.m_pRight)) + 1 ;
 	return pNode ;
end


function dumpAVGTree(root)
	local extractAVGTree = nil ;
	extractAVGTree = function(root,str,index)
		str[index] = str[index] or "" ;
		str[index] = str[index] .. root.m_nvalue .. "    ";
		if(root.m_pLeft) then
			extractAVGTree(root.m_pLeft,str,index+1) ;
		end

		if(root.m_pRight) then
			extractAVGTree(root.m_pRight,str,index+1);
		end
	end
	local str = {} ;
	extractAVGTree(root,str,1);
	local len = 0 ;
	for k,v in pairs(str) do
		len = len + 1 ;
	end
	print("len-->"..len)
	for i=0,len do
		print("***->"..(str[i] or ""));
	end
end


local data = {10,9,8,7,6,5,4,3,2,1};
local root = nil ;
for i=1,#data do
	root = insertNode(data[i],root);
end

dumpAVGTree(root);

--
-- 假定当前节点 
-- 遍历结束后当前节点的左边节点肯定是左子树里边最后边的结点
-- 遍历结束后当前节点的右边节点肯定是左子树里边最左边的结点
--		 	4
--	  2     	   8
--  1   3 		 6   9
--       	   5   7   10
-- --迭代访问节点
function ConvertNode(pNode,asRight)
	if(not pNode) then
		return ;
	end
	local pLeft,pRight ;
	--递归找到左节点
	if(pNode.m_pLeft) then
		pLeft = ConvertNode(pNode.m_pLeft,false)
	end
	if(pLeft) then
		pLeft.m_pRight = pNode ;
		pNode.m_pLeft = pLeft ;
	end

	if(pNode.m_pRight) then
		pRight = ConvertNode(pNode.m_pRight,true)
	end

	if (pRight) then
		pNode.m_pRight = pRight ;
		pRight.m_pLeft = pNode ; 
	end

	local pTemp = pNode ;

	--如果是访问右节点 返回 最左节点
	if asRight then
		while(pTemp.m_pLeft) do
			pTemp = pTemp.m_pLeft ;
		end
	else
		while(pTemp.m_pRight) do
			pTemp = pTemp.m_pRight ;
		end
	end
	return pTemp ;
end


root = ConvertNode(root,true)

while(root) do
	print(root.m_nvalue);
	root = root.m_pRight ;
end

---中序遍历 设置联系就好
-- function MiddleErgodic(pNode)
-- 	if pNode.m_pLeft then
-- 		MiddleErgodic(pNode.m_pLeft);
-- 	end
-- 	print(pNode.m_nvalue) ;
-- 	if pNode.m_pRight then
-- 		MiddleErgodic(pNode.m_pRight);
-- 	end

-- end
-- MiddleErgodic(root)